def adjacency_matrix_to_edge_list(adjacency_matrix):
n = len(adjacency_matrix)
edge_list = []
for i in range(n):
for j in range(i+1, n):
if adjacency_matrix[i][j] == 1:
edge_list.append((i+1, j+1))
return edge_list
# Ввод количества вершин и матрицы смежности
n = int(input("Введите количество вершин: "))
adjacency_matrix = []
for _ in range(n):
row = list(map(int, input().split()))
adjacency_matrix.append(row)
# Преобразование матрицы смежности в список ребер
edge_list = adjacency_matrix_to_edge_list(adjacency_matrix)
# Вывод списка ребер
for edge in edge_list:
print(edge[0], edge[1])
В этой программе определена функция adjacency_matrix_to_edge_list
, которая принимает матрицу смежности в качестве аргумента и возвращает список ребер. Функция проходит по каждой паре вершин в графе и проверяет, есть ли между ними ребро (1 в матрице смежности). Если ребро есть, то добавляется соответствующая пара вершин в список ребер.
Программа сначала запрашивает количество вершин в графе, а затем построчно вводит матрицу смежности. После этого матрица смежности преобразуется в список ребер с помощью функции adjacency_matrix_to_edge_list
. Наконец, программа выводит список ребер.
Например, при вводе следующей матрицы смежности для графа с 4 вершинами:
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
Программа выведет:
1 2
1 3
2 4
3 4
То есть список ребер заданного графа будет выглядеть так: [(1, 2), (1, 3), (2, 4), (3, 4)].
Также программа
m = (map(int, input().split()) for _ in range(int(input('Num of nodes: '))))
edgs = {frozenset([ci+1, ni+1]) for ni, ne in enumerate(m) for ci, ce in enumerate(ne) if ce == 1}
print([tuple(x) for x in edgs])
Num of nodes: 6
1 1 0 0 1 0
1 0 1 0 1 0
0 1 0 1 0 0
0 0 1 0 1 1
1 1 0 1 0 0
0 0 0 1 0 0
[(1, 2), (1, 5), (3, 4), (2, 3), (4, 6), (2, 5), (1,), (4, 5)]